package com.wxm.question.q1;

import java.util.List;
import java.util.Stack;

public class Tree {
    private TreeNode root;

    public Tree(TreeNode root) {
        this.root = root;
    }

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    /**
     * 后序遍历
     * 头 右 左 -> 压栈取反 -> 左 右 头
     * @param tree
     */
    private static Stack<TreeNode> reserveStack = null;

    public static TreeNode getNextTreeNode(Tree tree) {
        TreeNode head = tree.getRoot();
        if (head == null){
            return null;
        }

        Stack<TreeNode> stack1 = new Stack<>();

        stack1.push(head);
        if (reserveStack == null){
            reserveStack = new Stack<>();
        } else {
            return reserveStack.isEmpty() ? null : reserveStack.pop();
        }

        while (!stack1.isEmpty()){
            head = stack1.pop();
            reserveStack.push(head);
            List<TreeNode> children = head.getChildren();
            if(children != null && !children.isEmpty()){
                for (TreeNode child : children) {
                    stack1.push(child);
                }
            }
        }

        return reserveStack.isEmpty() ? null : reserveStack.pop();
    }
}
